class Solution:
    def dfs(self, grid, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
            return
        if grid[i][j] == '1':
            grid[i][j] = '2'
            self.dfs(grid, i - 1, j)
            self.dfs(grid, i + 1, j)
            self.dfs(grid, i, j - 1)
            self.dfs(grid, i, j + 1)

    # def dfs(self, grid, i, j):
    #     grid[i][j] = '0'
    #     if (i > 0 and grid[i - 1][j] == '1'):
    #         self.dfs(grid, i - 1, j)
    #     if (j > 0 and grid[i][j - 1] == '1'):
    #         self.dfs(grid, i, j - 1)
    #     if (i < len(grid) - 1 and grid[i + 1][j] == '1'):
    #         self.dfs(grid, i + 1, j)
    #     if (j < len(grid[0]) - 1 and grid[i][j + 1] == '1'):
    #         self.dfs(grid, i, j + 1)

    def numIslandsCore(self, grid, i, j, high, width):
        if i >= high or j >= width:
            return 1
        elif grid[i][j] == '0':
            return 1
        elif grid[i][j] == '1':
            grid[i][j] = '*'
            num1 = self.numIslandsCore(grid, i + 1, j, high, width)
            num2 = self.numIslandsCore(grid, i, j + 1, high, width)
            if j >= 1 and grid[i][j - 1] == '1':
                num3 = self.numIslandsCore(grid, i, j - 1, high, width)
                if num1 or num2 or num3:
                    return 1
                else:
                    return 0
            if i >= 1 and grid[i - 1][j] == '1':
                num3 = self.numIslandsCore(grid, i - 1, j, high, width)
                if num1 or num2 or num3:
                    return 1
                else:
                    return 0
            if num1 or num2:
                return 1
            else:
                return 0

    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if len(grid) == 0:
            return 0
        high = len(grid)
        width = len(grid[0])
        island_num = 0
        for i in range(high):
            for j in range(width):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    island_num += 1
        return island_num


islands_list = [["1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "0", "1", "1"],
                ["0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "0"],
                ["1", "0", "1", "1", "1", "0", "0", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
                ["1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
                ["1", "0", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
                ["1", "0", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1"],
                ["0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "0", "1", "1", "1", "1"],
                ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "0", "1", "1"],
                ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
                ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
                ["0", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
                ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
                ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
                ["1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1"],
                ["1", "0", "1", "1", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1", "1", "0", "1", "1", "1"],
                ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "0"],
                ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "0", "0"],
                ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
                ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
                ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"]]
sol = Solution()
print(sol.numIslands(islands_list))
